Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cocktail/lalr.lha/lalr/src/Compress.mi

Text File | 1992-08-18 | 6KB | 265 lines

(* compress parse table *)

(* $Id: Compress.mi,v 2.2 1992/08/07 15:22:49 grosch rel $ *)

(* $Log: Compress.mi,v $
 * Revision 2.2  1992/08/07  15:22:49  grosch
 * allow several scanner and parsers; extend module Errors
 *
 * Revision 2.1  1991/11/21  14:53:14  grosch
 * new version of RCS on SPARC
 *
 * Revision 2.0  91/03/08  18:31:39  grosch
 * turned tables into initialized arrays (in C)
 * moved mapping tokens -> strings from Errors to Parser
 * changed interface for source position
 *
 * Revision 1.1  90/06/12  16:53:48  grosch
 * renamed main program to lalr, added { } for actions, layout improvements
 *
 * Revision 1.0     88/10/04  14:35:59  vielsack
 * Initial revision
 *
 *)

IMPLEMENTATION MODULE Compress;

FROM Automaton    IMPORT tIndex, tStateIndex;
FROM DynArray    IMPORT MakeArray, ExtendArray;
FROM Gen    IMPORT tTableLine, NoState, LastReadState, FirstTerminal, LastTerminal, FirstSymbol, LastSymbol;
FROM General    IMPORT Max, Min;
FROM SYSTEM    IMPORT TSIZE;
FROM TokenTab    IMPORT Vocabulary;

  CONST
    InitTableMax = 1500;
    InitNTableMax = 500;

PROCEDURE InitCompressTable;
   VAR
      b        : tIndex;
      State    : tStateIndex;
   BEGIN
      BaseCount       := LastReadState+1;
      MakeArray (Base,BaseCount,ElmtSize);

      DefaultCount := LastReadState+1;
      MakeArray (Default,DefaultCount,ElmtSize);

      ControlCount := LastSymbol+InitTableMax;
      MakeArray (Control,ControlCount,TSIZE(ControlType));

      TableMax := ControlCount - 1;

      FOR State := 0 TO LastReadState DO
     Base^ [State] := 0;
     Default^ [State] := NoState;
      END;

      FOR b := 0 TO TableMax DO
     Control^ [b].Next  := NoState;
     Control^ [b].Check := NoState;
      END;

      TableSize := 0;
    END InitCompressTable;

PROCEDURE CompressTableLine (State: tStateIndex; DefaultState: tStateIndex; VAR TableLine: tTableLine);

(* Terminale komprimieren *)

   VAR
      b        : tIndex;
      Success    : BOOLEAN;
      Symbol    : Vocabulary;
      index    : tIndex;
      OldTableMax : tIndex;
      NextSym    : ARRAY Vocabulary OF Vocabulary;
      StartSym    ,
      StopSym    ,
      PrevSym    : Vocabulary;

   BEGIN

      Default^ [State] := DefaultState;

      (* solution 2 *)

      (* turn the row Table [State, ...] into a list *)

      Symbol := FirstTerminal;
      Success := FALSE;
      LOOP
     IF Symbol > LastTerminal THEN EXIT; END;
     IF (TableLine [Symbol] # NoState) THEN
        StartSym := Symbol;
        PrevSym  := Symbol;
        Success  := TRUE;
        EXIT;
     END;
     INC (Symbol);
      END;
      INC (Symbol);

      LOOP
     IF Symbol > LastTerminal THEN EXIT; END;
     IF (TableLine [Symbol] # NoState) THEN
        NextSym [PrevSym] := Symbol;
        PrevSym := Symbol;
     END;
     INC (Symbol);
      END;
      StopSym := PrevSym;

      (* search for a usable base b *)

      b := 0;
      IF Success THEN
     LOOP
        Success := TRUE;
        Symbol := StartSym;
        LOOP
           IF (Control^ [b + Symbol].Check    # NoState) THEN
          Success := FALSE;
          EXIT;
           END;
           IF Symbol = StopSym THEN EXIT; END;
           Symbol := NextSym [Symbol];
        END;

        IF Success THEN EXIT; END;
        INC (b);
        IF b + LastTerminal > TableMax THEN
           OldTableMax := TableMax;
           ExtendArray (Control,ControlCount,TSIZE(ControlType));
           TableMax := ControlCount - 1;
           FOR index := OldTableMax+1 TO TableMax DO
          Control^ [index].Next     := NoState;
          Control^ [index].Check := NoState;
           END;
        END;
     END;
      ELSE
     Success := TRUE;
      END;

      Base^ [State] := b;
      TableSize := Max (TableSize, b);
      FOR Symbol := FirstTerminal TO LastTerminal DO
     IF (TableLine [Symbol] # NoState) THEN
        Control^ [b + Symbol].Check := State;
        Control^ [b + Symbol].Next    := TableLine [Symbol];
        INC (Filling);
     END;
      END;
   END CompressTableLine;


PROCEDURE InitCompressNTable;
   VAR
      b        : tIndex;
      State    : tStateIndex;
   BEGIN
      NBaseCount := LastReadState+1;
      MakeArray (NBase,NBaseCount,ElmtSize);
      NNextCount := LastSymbol+InitNTableMax;
      MakeArray (NNext,NNextCount,TSIZE(TableElmt));
      NTableMax := NNextCount - 1;
      FOR State := 0 TO LastReadState DO NBase^ [State] := 0; END;
      FOR b := 0 TO NTableMax DO NNext^ [b] := NoState; END;
      NTableSize := 0;
    END InitCompressNTable;

PROCEDURE CompressNTableLine (State: tStateIndex; VAR TableLine: tTableLine);

(* Nichtterminale komprimieren *)

   VAR
      b        : tIndex;
      Success    : BOOLEAN;
      Symbol    : Vocabulary;
      index    : tIndex;
      OldTableMax : tIndex;
      NextSym    : ARRAY Vocabulary OF Vocabulary;
      StartSym    ,
      StopSym    ,
      PrevSym    : Vocabulary;

   BEGIN

      (* solution 2 *)

      (* turn the row Table [State, ...] into a list *)

      Symbol := LastTerminal+1; (* FirstNonterminal *)
      Success := FALSE;
      LOOP
     IF Symbol > LastSymbol THEN EXIT; END;
     IF (TableLine [Symbol] # NoState) THEN
        StartSym := Symbol;
        PrevSym  := Symbol;
        Success  := TRUE;
        EXIT;
     END;
     INC (Symbol);
      END;
      INC (Symbol);

      LOOP
     IF Symbol > LastSymbol THEN EXIT; END;
     IF (TableLine [Symbol] # NoState) THEN
        NextSym [PrevSym] := Symbol;
        PrevSym := Symbol;
     END;
     INC (Symbol);
      END;
      StopSym := PrevSym;

      (* search for a usable base b *)

      b := 0;
      IF Success THEN
     LOOP
        Success := TRUE;
        Symbol := StartSym;
        LOOP
           IF (NNext^ [b + Symbol] # NoState) AND
          (NNext^ [b + Symbol] # TableLine [Symbol]) THEN
          Success := FALSE;
          EXIT;
           END;
           IF Symbol = StopSym THEN EXIT; END;
           Symbol := NextSym [Symbol];
        END;

        IF Success THEN EXIT; END;
        INC (b);
        IF b + LastSymbol > NTableMax THEN
           OldTableMax := NTableMax;
           ExtendArray (NNext,NNextCount,TSIZE(TableElmt));
           NTableMax := NNextCount - 1;
           FOR index := OldTableMax+1 TO NTableMax DO
          NNext^ [index] := NoState;
           END;
        END;
     END;
      ELSE
     Success := TRUE;
      END;

      NBase^ [State] := b;
      NTableSize := Max (NTableSize, b);
      FOR Symbol := LastTerminal+1 TO LastSymbol DO
     IF (TableLine [Symbol] # NoState) THEN
        NNext^ [b + Symbol] := TableLine [Symbol];
        INC (NFilling);
     END;
      END;
   END CompressNTableLine;

BEGIN
  ElmtSize    := TSIZE(TableElmt);
  Filling    := 0;
  NFilling    := 0;
END Compress.